/**
 * 给你一个整数数组 nums ，判断是否存在三元组 [nums[i], nums[j], nums[k]] 满足 i != j、i != k 且 j != k ，
 * 同时还满足 nums[i] + nums[j] + nums[k] == 0 。请你返回所有和为 0 且不重复的三元组。
 *
 * 注意：答案中不可以包含重复的三元组。
 */

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

public class Solution {
    public List<List<Integer>> threeSum(int[] nums) {
        Arrays.sort(nums);
        int cur = 0;
        List<List<Integer>> ret =  new ArrayList<List<Integer>>();
        while(cur < nums.length-2){
            if(nums[cur] > 0) break;
            int left = cur+1;
            int right = nums.length - 1;
            int target = -nums[cur];
            while(left <right){
                List<Integer> tmp = new ArrayList<Integer>();
                int sum = nums[left] + nums[right];
                if(sum == target){
                    tmp.add(nums[cur]);
                    tmp.add(nums[left]);
                    tmp.add(nums[right]);
                    ret.add(tmp);
                    while( left < nums.length-1 && nums[left] == nums[left+1]){
                        left++;
                    }
                    left++;
                    while( right > 0 && nums[right] == nums[right-1]){
                        right--;
                    }
                    right--;

                }else if(sum < target){
                    while( left < nums.length-1 && nums[left] == nums[left+1]){
                        left++;
                    }
                    left++;
                }else{
                    while(right > 0 &&nums[right] == nums[right-1]){
                        right--;
                    }
                    right--;
                }

            }
            while( cur <nums.length -2 &&nums[cur] == nums[cur+1]){
                cur++;
            }
            cur++;
        }
        return ret;
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1,-1,-1,0};
        Solution solution = new Solution();
        List<List<Integer>> ret = solution.threeSum(nums);
        System.out.println(ret);
    }
}